#include <stdio.h>

void swap(int *, int *);
void qs(int *, int, int);
int pt(int *, int, int);

void swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

void qs(int *sz, int l, int h)
{
    if (l < h)
    {
        int p = pt(sz, l, h);
        qs(sz, l, p-1);
        qs(sz, p+1, h);
    }
}

int pt(int *sz, int l, int h)
{
    int base = sz[h];   // 以最右边作为基准
    int i = l;
    int temp;
    for (int j = l; j < h; j++)
    {
        if (sz[j] <= base)
        {
            swap(&sz[j], &sz[i]);
            i++;
            // printf("%s", "yes");
        }
    }
    swap(&sz[i], &sz[h]);
    return i;
}

int main()
{
    // printf("Hello world\n");
    int a[5] = {9, 2, 8, 6, 0};
    qs(a, 0, 4);
    for (int i = 0; i < 5; i++)
        printf("%d\n", a[i]);
    return 0;
}

